package org.usmile.algorithms.leetcode.hard;

import java.util.ArrayDeque;

/**
 * 84. 柱状图中最大的矩形
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 * 示例 2：
 * 输入： heights = [2,4]
 * 输出： 4
 *
 * 提示：
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */
public class _0084 {
}

// 枚举高 + 单调栈
class _0084_Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 1. 计算每根柱子左边第一个小于这根柱子的柱子(每根柱子的左边界)
        int[] left = new int[n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            left[stack.pop()] = -1;
        }
        // 2. 计算每根柱子右边第一个小于这根柱子的柱子(每根柱子的右边界)
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            right[stack.pop()] = n;
        }

        int maxArea = 0;
        for (int mid = 0; mid < n; mid++) {
            int height = heights[mid];
            maxArea = Math.max(maxArea, height * (right[mid] - left[mid] - 1));
        }

        return maxArea;
    }
}

// 枚举宽
class _0084_Solution1 {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for (int left = 0; left < heights.length; left++) {
            int minHeight = heights[left];
            for (int right = left; right < heights.length; right++) {
                minHeight = Math.min(minHeight, heights[right]);
                // [left, right]
                int currWidth = right - left + 1;
                maxArea = Math.max(maxArea, minHeight * currWidth);
            }
        }

        return maxArea;
    }
}

// 枚举高
class _0084_Solution2 {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        for (int mid = 0; mid < n; mid++) {
            int height = heights[mid];

            // 确定左右边界
            int left = mid, right = mid;
            while (left >= 0 && heights[left] >= height) {
                left--;
            }
            while (right < n && heights[right] >= height) {
                right++;
            }

            maxArea = Math.max(maxArea, height * (right - left - 1));
        }

        return maxArea;
    }
}